package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PermuteUnique {

	public List<List<Integer>> permuteUnique(int[] nums){
		List<List<Integer>> result = new ArrayList<>();
		backtracking(nums, 0, result);
		return result;
	}
	
	private void backtracking(int[] nums, int startIndex, List<List<Integer>> result) {
		
		if(startIndex == nums.length) {
			result.add(Arrays.stream(nums).boxed().toList());
		}else {
			Set<Integer> set = new HashSet<>();
			for(int i = startIndex; i < nums.length; i++) {
				if(set.contains(nums[i])) continue;
				set.add(nums[i]);
				swap(nums, startIndex, i);
				backtracking(nums, startIndex + 1, result);
				swap(nums, startIndex, i);
			}
		}
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}
